Kupiec

Limit pamięci: 64 MB

W Bajtlandii sieć dróg między miastami jest taka, że między dwoma dowolnymi miastami istnieje dokładnie jedna droga (bezpośrednia lub pośrednia). Pewien kupiec przyjechał do Bajtlandii w celach zarobokowych. Pierwszego dnia chciałby zamieszkać w dowolnym mieście (miasto początkowe), a następnie udać się do wybranego miasta (miasto końcowe). Kupiec na drodze z jednego miasta do drugiego nie może dwa razy odwiedzić tego samego miasta, ze względu na przepisy prawne Bajtalndii. Chciałby jednak wybrać miasto początkowe i końcowe w taki sposób, aby jego zarobek był jak największy.

Kupiec zarabia poruszając się pomiędzy miastami. Dla każdego bezpośredniego połączenia wiemy, ile bajtalarów kupiec zarobi lub straci. Pomóż wybrać kupcowi dwa miasta tak, aby jego zarobek był jak największy (w szczególności miasto początkowe i końcowe może być tym samym miastem).

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita (). W następnych wierszach po trzy liczby całkowite (), oznaczające, że istnieje bezpośrednie połączenie między miastami i , w którym kupiec zarobi bajtalarów (ujemne oznacza stratę kupca).

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba cakłkowita oznaczająca maksymalny zarobek kupca.

Przykład

Dla danych wejściowych:

6
1 3 3
3 2 2
4 3 2
3 5 -1
5 6 4

poprawną odpowiedzią jest:

6

Autor zadania: Jacek Tomasiewicz.